class Solution {
    /**
     * 声明 不是自己写出来的e
     * @param s
     * @param p
     * @return
     */
    public boolean isMatch(String s, String p) {
        boolean[][] dp=new boolean[s.length()+1][p.length()+1];
        dp[0][0]=true;
        for (int i=2;i<=p.length();i++){
            dp[0][i]=p.charAt(i-1)=='*'&&dp[0][i-2];
        }
        for (int i=0;i<s.length();i++){
            for (int j=0;j<p.length();j++){
                if (p.charAt(j)=='*'){
                    dp[i+1][j+1]=dp[i+1][j-1]||
                            (dp[i][j+1]&&headMatched(s,p,i,j-1));
                }else {

                    dp[i+1][j+1]=dp[i][j]&&headMatched(s,p,i,j);
                }
            }
        }
        return dp[s.length()][p.length()];
    }
    public boolean headMatched(String s,String p,int i,int j){
        return s.charAt(i)==p.charAt(j)||p.charAt(j)=='.';
    }
}
